#include "base.h"

/**
 Definition for singly-linked list.**/
struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

class Solution
{
public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *merge_head, *merge = nullptr;
        if (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                merge_head = merge = list1;
                list1 = list1->next;
            }
            else
            {
                merge_head = merge = list2;
                list2 = list2->next;
            }
        }
        else if (list1)
        {
            return list1;
        }
        else if (list2)
        {
            return list2;
        }
        else
        {
            return nullptr;
        }
        while (list1 && list2)
        {
            if (list1->val < list2->val)
            {
                merge->next = list1;
                list1 = list1->next;
            }
            else
            {
                merge->next = list2;
                list2 = list2->next;
            }
            merge = merge->next;
        }

        if (list1)
        {
            merge->next = list1;
        }
        else if (list2)
        {
            merge->next = list2;
        }
        return merge;
    }
};

ListNode *make_arr_node_list(int arr[], int n)
{
    ListNode *a, *b = nullptr;
    a = b = new ListNode(arr[0]);
    for (int i = 1; i < n; i++)
    {
        a->next = new ListNode(arr[i]);
        a = a->next;
    }
    return b;
}

void main()
{
    int arr1[] = {1, 2, 4};
    int arr2[] = {1, 3, 4};
    auto a = make_arr_node_list(arr1, 3);
    auto b = make_arr_node_list(arr2, 3);
    Solution().mergeTwoLists(a, b);
}